#include <iostream>
#include <stack>
#include <string>
using namespace std;

//class Solution {
//public:
//    int calculate(string s) {
//        stack<int> st;
//        char ch = '+';
//        int i = 0;
//        while (i < s.size())
//        {
//            while (s[i] == ' ') i++;
//            if (i == s.size()) break;
//            if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
//            {
//                ch = s[i];
//                i++;
//            }
//            else
//            {
//                int tmp = s[i++] - '0';
//                while (i < s.size() && s[i] >= '0' && s[i] <= '9')
//                {
//                    tmp = tmp * 10 + (s[i] - '0');
//                    i++;
//                }
//                //
//                if (ch == '+') st.push(tmp);
//                else if (ch == '-') st.push(-tmp);
//                else if (ch == '*') st.top() *= tmp;
//                else st.top() /= tmp;
//            }
//        }
//        int ret = 0;
//        while (!st.empty())
//        {
//            ret += st.top();
//            st.pop();
//        }
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution s;
//    string k = "  30";
//    int ret = s.calculate(k);
//    cout << ret;
//    return 0;
//}

//class Solution {
//public:
//    string decodeString(string s) {
//        stack<string> strst;
//        stack<int> numst;
//        int i = 0;
//        int n = s.size();
//        strst.push("");//
//        while (i < n)
//        {
//            if (s[i] >= '0' && s[i] <= '9')
//            {
//                int tmp = s[i++] - '0';
//                while (i < n && s[i] >= '0' && s[i] <= '9')
//                {
//                    tmp = tmp * 10 + (s[i] - '0');
//                    i++;
//                }
//                numst.push(tmp);
//            }
//            else if (s[i] == '[')
//            {
//                string tmp;
//                i++;
//                while (i < n && s[i] >= 'a' && s[i] <= 'z')
//                {
//                    tmp += s[i];
//                    i++;
//                }
//                strst.push(tmp);
//            }
//            else if (s[i] == ']')
//            {
//                int k = numst.top();
//                numst.pop();
//                string tmp = strst.top();
//                strst.pop();
//                string str = "";
//                while (k--)
//                {
//                    str += tmp;
//                }
//                // strst.push(str);XXX
//                strst.top() += str;//
//                i++;
//            }
//            else
//            {
//                string tmp;
//                tmp += s[i];
//                i++;
//                while (i < n && s[i] >= 'a' && s[i] <= 'z')
//                {
//                    tmp += s[i];
//                    i++;
//                }
//                strst.top() += tmp;
//            }
//        }
//        return strst.top();
//    }
//};


//class MinStack {
//public:
//    /** initialize your data structure here. */
//    stack<int> st;
//    stack<int> minst;
//    MinStack() {
//
//    }
//
//    void push(int x) {
//        st.push(x);
//        if (minst.empty() || x <= minst.top())
//        {
//            minst.push(x);
//        }
//    }
//
//    void pop() {
//        if (st.top() == minst.top())
//        {
//            minst.pop();
//        }
//        st.pop();
//    }
//
//    int top() {
//        return st.top();
//    }
//
//    int getMin() {
//        return minst.top();
//    }
//};

//class Solution {
//public:
//    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
//        stack<int> st;
//        int j = 0;
//        for (int i = 0; i < pushed.size(); i++)
//        {
//            st.push(pushed[i]);
//            while (!st.empty() && st.top() == popped[j])
//            {
//                st.pop();
//                j++;
//            }
//        }
//        if (j == popped.size()) return true;
//        return false;
//    }
//};

